package problems

// 303
// https://leetcode-cn.com/problems/range-sum-query-immutable/
type NumArray struct {
	nums []int
}

func NumArrayConstructor(nums []int) NumArray {
	var newNums = make([]int, len(nums)+1)
	for k, v := range nums {
		newNums[k+1] = v + newNums[k]
	}
	return NumArray{newNums}
}

func (n *NumArray) SumRange(i int, j int) int {
	if i < 0 {
		i = len(n.nums) + i
	}
	if j < 0 {
		j = len(n.nums) + j
	}
	return n.nums[j+1] - n.nums[i]
}

// 304
// https://leetcode-cn.com/problems/range-sum-query-2d-immutable/
type NumMatrix struct {
	matrix [][]int
}

func NumMatrixConstructor(matrix [][]int) NumMatrix {
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			if i > 0 {
				matrix[i][j] += matrix[i-1][j]
			}
			if j > 0 {
				matrix[i][j] += matrix[i][j-1]
			}
			if i > 0 && j > 0 {
				matrix[i][j] -= matrix[i-1][j-1]
			}
		}
	}
	return NumMatrix{matrix}
}

func (n *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	var sum = n.matrix[row2][col2]
	if row1 > 0 {
		sum -= n.matrix[row1-1][col2]
	}
	if col1 > 0 {
		sum -= n.matrix[row2][col1-1]
	}
	if row1 > 0 && col1 > 0 {
		sum += n.matrix[row1-1][col1-1]
	}
	return sum
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */

// 326
// https://leetcode-cn.com/problems/power-of-three/
func IsPowerOfThree(n int) bool {
	for n > 1 {
		if n%3 != 0 {
			return false
		}
		n /= 3
	}
	return n == 1
}

// 331
// https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/
func IsValidSerialization(preorder string) bool {
	preorder = `,` + preorder
	var b byte
	count := 0
	for i := len(preorder) - 1; i >= 0; i-- {
		switch preorder[i] {
		case ' ':
		case ',':
			if b != '#' {
				if count < 2 {
					return false
				}
				count--
			}
		case '#':
			count++
		default:
		}
		b = preorder[i]
	}
	return count == 1
}

// 337
// https://leetcode-cn.com/problems/house-robber-iii/
func Rob(root *TreeNode) int {
	var order func(root *TreeNode) int
	var nodes = make(map[*TreeNode]int)
	order = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		if v, ok := nodes[root]; ok {
			return v
		}
		var rob1, rob2 = 0, 0
		if root.Left != nil {
			rob2 += order(root.Left.Left) + order(root.Left.Right)
		}
		if root.Right != nil {
			rob2 += order(root.Right.Left) + order(root.Right.Right)
		}
		rob2 += root.Val
		rob1 = order(root.Left) + order(root.Right)
		if rob1 < rob2 {
			rob1 = rob2
		}
		nodes[root] = rob1
		return rob1
	}
	return order(root)
}

// 338
// https://leetcode-cn.com/problems/counting-bits/
func CountBits(num int) []int {
	nums := []int{0}
	for i := 1; i <= num; i++ {
		nums = append(nums, nums[i>>1]+(i&1))
	}
	return nums
}

// 341
// https://leetcode-cn.com/problems/flatten-nested-list-iterator/

type NestedIterator struct {
	nums  []int
	index int
}

func ConstructorNestedIterator(nestedList []*NestedInteger) *NestedIterator {
	n := &NestedIterator{nums: []int{}, index: 0}
	for len(nestedList) > 0 {
		last := nestedList[len(nestedList)-1]
		nestedList = nestedList[:len(nestedList)-1]
		if !last.IsInteger() {
			nestedList = append(nestedList, last.GetList()...)
		} else {
			n.nums = append(n.nums, last.GetInteger())
		}
	}
	n.index = len(n.nums)
	return n
}
func (n *NestedIterator) Next() int {
	next := n.nums[n.index]
	n.index--
	return next
}
func (n *NestedIterator) HasNext() bool {
	return n.index >= 0
}

// 343 TODO
// https://leetcode-cn.com/problems/power-of-four/
func IsPowerOfFour(num int) bool {
	if num <= 0 || num&(num-1) != 0 {
		return false
	}
	return num%3 == 1
}

// 344
// https://leetcode-cn.com/problems/reverse-string/
func ReverseString(s []byte) {
	var left, right = 0, len(s) - 1
	for left <= right {
		s[left], s[right] = s[right], s[left]
		left++
		right--
	}
}

// 345
// https://leetcode-cn.com/problems/reverse-vowels-of-a-string/
func ReverseVowels(s string) string {
	var vowels = map[rune]struct{}{
		'a': {}, 'e': {}, 'i': {}, 'o': {}, 'u': {},
		'A': {}, 'E': {}, 'I': {}, 'O': {}, 'U': {},
	}
	var indexes []int
	var sArr = []rune(s)
	for k, v := range sArr {
		if _, ok := vowels[v]; ok {
			indexes = append(indexes, k)
		}
	}
	var left, right = 0, len(indexes) - 1
	for left <= right {
		sArr[indexes[left]], sArr[indexes[right]] = sArr[indexes[right]], sArr[indexes[left]]
		left++
		right--
	}
	return string(sArr)
}

// 347
// https://leetcode-cn.com/problems/top-k-frequent-elements/
func TopKFrequent(nums []int, k int) []int {
	var numsCount = make(map[int]int)
	var orderNums = make([][]int, len(nums))
	for _, v := range nums {
		numsCount[v]++
		orderNums[numsCount[v]-1] = append(orderNums[numsCount[v]-1], v)
	}
	var res []int
	var count = k
	for i := len(orderNums) - 1; i >= 0 && count > 0; i-- {
		for j := 0; j < len(orderNums[i]) && count > 0; j++ {
			if _, ok := numsCount[orderNums[i][j]]; ok {
				delete(numsCount, orderNums[i][j])
				res = append(res, orderNums[i][j])
				count--
			}
		}
	}
	return res
}

// 349
// https://leetcode-cn.com/problems/intersection-of-two-arrays/
func Intersection(nums1 []int, nums2 []int) []int {
	if len(nums1) > len(nums2) {
		nums1, nums2 = nums2, nums1
	}
	var nums3 = make(map[int]bool)
	for _, v := range nums1 {
		nums3[v] = false
	}
	for _, v := range nums2 {
		if _, ok := nums3[v]; ok {
			nums3[v] = true
		}
	}
	var res []int
	for k, v := range nums3 {
		if v {
			res = append(res, k)
		}
	}
	return res
}

// 350
// https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
func Intersect(nums1 []int, nums2 []int) []int {
	if len(nums1) > len(nums2) {
		nums1, nums2 = nums2, nums1
	}
	var nums3 = make(map[int]int)
	var res []int
	for _, v := range nums1 {
		nums3[v]++
	}
	for _, v := range nums2 {
		if _, ok := nums3[v]; ok {
			if nums3[v] > 0 {
				res = append(res, v)
				nums3[v]--
			}
		}
	}
	return res
}

// 367
// https://leetcode-cn.com/problems/valid-perfect-square/
func IsPerfectSquare(num int) bool {
	if num < 1 {
		return false
	}
	var x = num
	for x*x > num {
		x = (x + num/x) / 2
	}
	return x*x == num
}

// 371
// https://leetcode-cn.com/problems/sum-of-two-integers/
func GetSum(a int, b int) int {
	for b != 0 {
		a, b = a^b, a&b<<1
	}
	return a
}

// 374
// https://leetcode-cn.com/problems/guess-number-higher-or-lower/
/**
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * func guess(num int) int;
 */
func GuessNumber(n int) int {
	guess := func(num int) int {
		var des = 6
		if num < des {
			return 1
		} else if num > des {
			return -1
		}
		return 0
	}
	var l, r = 1, n
	for l <= r {
		var num = (l + r) / 2
		switch guess(num) {
		case 1:
			l = num + 1
		case -1:
			r = num - 1
		default:
			return num
		}
	}
	return 0
}

// 383
// https://leetcode-cn.com/problems/ransom-note/
func CanConstruct(ransomNote string, magazine string) bool {
	var arr = make(map[byte]int)
	for i := 0; i < len(ransomNote); i++ {
		if _, ok := arr[ransomNote[i]]; !ok {
			arr[ransomNote[i]] = 0
		}
		arr[ransomNote[i]]++
	}
	for i := 0; i < len(magazine); i++ {
		if _, ok := arr[magazine[i]]; ok {
			arr[magazine[i]]--
			if arr[magazine[i]] == 0 {
				delete(arr, magazine[i])
			}
		}
	}
	return len(arr) == 0
}

// 387
// https://leetcode-cn.com/problems/first-unique-character-in-a-string/
func FirstUniqChar(s string) int {
	var arr, indexes = make(map[byte]int), make(map[byte]int)
	for i := 0; i < len(s); i++ {
		if _, ok := arr[s[i]]; ok {
			arr[s[i]]++
			delete(indexes, s[i])
		} else {
			arr[s[i]] = 1
			indexes[s[i]] = i
		}
	}
	var index = -1
	for _, v := range indexes {
		if index == -1 || v < index {
			index = v
		}
	}
	return index
}

// 389
// https://leetcode-cn.com/problems/find-the-difference/
func FindTheDifference(s string, t string) byte {
	var arr = make([]int, 26)
	for _, v := range t {
		arr[v-'a']++
	}
	for _, v := range s {
		arr[v-'a']--
	}
	for k, v := range arr {
		if v == 1 {
			return byte(k + 'a')
		}
	}
	return 0
}

// 392
// https://leetcode-cn.com/problems/is-subsequence/
func IsSubsequence(s string, t string) bool {
	var si, ti = 0, 0
	for si < len(s) && ti < len(t) {
		if s[si] == t[ti] {
			si++
		}
		ti++
	}
	return si == len(s)
}
